package com.example.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 单调栈  ** 参考题解 ** 难点
 * 柱状图中最大的矩形
 */
public class Demo0084 {

    public static void main(String[] args) {

        int[] heights=new int[]{5,4,4,6,3,2,9,5,4,8,1,0,0,4,7,2};
        largestRectangleArea(heights);
    }

    public static int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int ans=0;
        Deque<Integer> stack=new ArrayDeque<>();
        //1.左哨兵
        stack.addFirst(-1);
        for (int i = 0; i < len; i++) {
            int curHigh=heights[i];

            /**
             * 左边界为-1理解为哨兵，右边界为len
             * 先出栈的定比当前出栈值要高
             * 出栈后在peekLast 与当前 i 或者len 中间为两边夹当前出栈  定宽和高
             */
            //1.考虑出栈
            while (stack.size()>1 && heights[stack.peekLast()]>curHigh){
                Integer curOut = stack.pollLast();
                ans=Math.max((i-stack.peekLast()-1)*heights[curOut],ans);
            }

            //2.不出栈则入栈
            stack.addLast(i);
        }

        //3.最终只入栈
        while (stack.size()>1){
            Integer high = stack.pollLast();
            ans=Math.max((len-stack.peekLast()-1)*heights[high],ans);
        }


        return ans;
    }
}
